package 困难.搜索.广度优先搜索;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

/**
 * 病毒扩散得很快，现在你的任务是尽可能地通过安装防火墙来隔离病毒。
 * 假设世界由 m x n 的二维矩阵 isInfected 组成， isInfected[i][j] == 0 
 * 表示该区域未感染病毒，而  isInfected[i][j] == 1 表示该区域已感染病毒。
 * 可以在任意 2 个相邻单元之间的共享边界上安装一个防火墙（并且只有一个防火墙）。
 * 每天晚上，病毒会从被感染区域向相邻未感染区域扩散，除非被防火墙隔离。现由
 * 于资源有限，每天你只能安装一系列防火墙来隔离其中一个被病毒感染的区域（一个
 * 区域或连续的一片区域），且该感染区域对未感染区域的威胁最大且 保证唯一 。
 * 你需要努力使得最后有部分区域不被病毒感染，如果可以成功，那么返回需要使用
 * 的防火墙个数; 如果无法实现，则返回在世界被病毒全部感染时已安装的防火墙个数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/contain-virus
 */
public class 隔离病毒_749 {

    public static void main(String[] args) {

//        int[][] isInfected = {{0, 1, 0, 0, 0, 0, 0, 1}, {0, 1, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 0}};
//        int[][] isInfected = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
        int[][] isInfected = {{1, 1, 1, 0, 0, 0, 0, 0, 0}, {1, 0, 1, 0, 1, 1, 1, 1, 1}, {1, 1, 1, 0, 0, 0, 0, 0, 0}};
//        int[][] isInfected = {{1}};
        System.out.println(new 隔离病毒_749().containVirus(isInfected));

    }

    private int[][] direction = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    /**
     * 思路：
     * 优先隔离感染最多区域的病毒
     * 步骤：
     * 获取感染最多的区域数量和防火墙数量
     * 其他病毒区域向外感染一层
     *
     * @param isInfected
     * @return
     */
    public int containVirus(int[][] isInfected) {
        int totalFireCount = 0;

        while (true) {
            int maxFire = getAndSetMaxFire(isInfected);
            totalFireCount += maxFire;
            // 没有地方可以设置防火墙
            if (maxFire == 0) {
                break;
            }
            // 病毒扩散一天
            spread(isInfected);
        }
        return totalFireCount;
    }

    // 向外传播一层
    private void spread(int[][] isInfected) {
        Set<String> set = new HashSet<>();
        for (int row = 0; row < isInfected.length; row++) {
            for (int column = 0; column < isInfected[row].length; column++) {
                if (!set.contains(row + "," + column) && isInfected[row][column] == 1) {
                    for (int[] direct : direction) {
                        int nextRow = row + direct[0];
                        int nextColumn = column + direct[1];
                        if (nextRow >= 0 && nextRow < isInfected.length &&
                                nextColumn >= 0 && nextColumn < isInfected[0].length) {
                            if (isInfected[nextRow][nextColumn] == 0) {
                                isInfected[nextRow][nextColumn] = 1;
                                set.add(nextRow + "," + nextColumn);
                            }
                        }
                    }
                }
            }
        }
    }

    public int containVirus2(int[][] isInfected) {
        int totalFireCount = 0;
        Deque<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < isInfected.length; i++) {
            for (int j = 0; j < isInfected[i].length; j++) {
                if (isInfected[i][j] == 1) {
                    queue.addLast(new int[]{i, j});
                }
            }
        }

        while (!queue.isEmpty()) {
            totalFireCount += getAndSetMaxFire(isInfected);

            // 病毒扩散一天
            Set<String> set = new HashSet<>();
            int size = queue.size();
            while (size-- > 0) {
                int[] curNode = queue.pollFirst();
                int row = curNode[0], column = curNode[1];
                if (isInfected[row][column] == 1) {
                    queue.addLast(curNode);
                    set.add(row + "," + column);
                    for (int[] direct : direction) {
                        int nextRow = row + direct[0];
                        int nextColumn = column + direct[1];
                        if (nextRow >= 0 && nextRow < isInfected.length &&
                                nextColumn >= 0 && nextColumn < isInfected[0].length &&
                                isInfected[nextRow][nextColumn] == 0 &&
                                !set.contains(nextRow + "," + nextColumn)) {
                            isInfected[nextRow][nextColumn] = 1;
                            queue.addLast(new int[]{nextRow, nextColumn});
                            set.add(nextRow + "," + column);
                        }
                    }
                }
            }
        }

        return totalFireCount;
    }

    private int getAndSetMaxFire(int[][] isInfected) {
        int maxFireCount = 0, maxAreaCount = 0;
        int[] fireNode = null;
        Set<String> set = new HashSet<>();
        for (int row = 0; row < isInfected.length; row++) {
            for (int column = 0; column < isInfected[row].length; column++) {
                if (!set.contains(row + "," + column) && isInfected[row][column] == 1) {
                    int[] curNode = {row, column};
                    Set<String> curSet = new HashSet<>();
                    int[] fireAndArea = getFireAndArea(curNode, isInfected, curSet);
                    // 当前节点相邻的病毒区域，无需再次进行搜索
                    set.addAll(curSet);
                    if (fireAndArea[1] >= maxAreaCount) {
                        maxAreaCount = fireAndArea[1];
                        maxFireCount = fireAndArea[0];
                        fireNode = curNode;
                    }
                }
            }
        }

        if (fireNode != null) {
            setFire(fireNode, isInfected);
        }

        return maxFireCount;
    }

    // 将当前连续病毒区域设置成防火墙
    private void setFire(int[] fireNode, int[][] isInfected) {
        int row = fireNode[0], column = fireNode[1];
        if (isInfected[row][column] == 1) {
            isInfected[row][column] = -1;
        }

        for (int[] direct : direction) {
            int nextRow = row + direct[0];
            int nextColumn = column + direct[1];

            if (nextRow >= 0 && nextRow < isInfected.length &&
                    nextColumn >= 0 && nextColumn < isInfected[0].length &&
                    isInfected[nextRow][nextColumn] == 1) {
                setFire(new int[]{nextRow, nextColumn}, isInfected);
            }
        }
    }

    // 获取当前节点所在的病毒连续区域需要设置的防火墙数量，和将要感染的区域数量
    private int[] getFireAndArea(int[] curNode, int[][] isInfected, Set<String> set) {
        int row = curNode[0], column = curNode[1];
        if (isInfected[row][column] != 1) {
            return new int[]{0, 0};
        }
        int fireCount = 0, areaCount = 0;

        set.add(row + "," + column);
        for (int[] direct : direction) {
            int nextRow = row + direct[0];
            int nextColumn = column + direct[1];

            if (nextRow >= 0 && nextRow < isInfected.length &&
                    nextColumn >= 0 && nextColumn < isInfected[0].length) {
                if (isInfected[nextRow][nextColumn] == 0) {
                    fireCount++;
                    // 区域需要去重，防火墙一个区域有四面，不需要去重
                    if (!set.contains(nextRow + "," + nextColumn)) {
                        areaCount++;
                        set.add(nextRow + "," + nextColumn);
                    }
                } else if (isInfected[nextRow][nextColumn] == 1 &&
                        !set.contains(nextRow + "," + nextColumn)) {
                    int[] fireAndArea = getFireAndArea(new int[]{nextRow, nextColumn}, isInfected, set);
                    fireCount += fireAndArea[0];
                    areaCount += fireAndArea[1];
                }
            }
        }

        return new int[]{fireCount, areaCount};
    }

}
